package graph.day15;

import java.util.ArrayList;
import java.util.List;

public class Leetcode_236 {

    List<TreeNode> tmpPath = new ArrayList<>();

    List<List<TreeNode>> paths = new ArrayList<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p);
        List<TreeNode> path1 = paths.get(0);
        tmpPath.clear();
        dfs(root, q);
        List<TreeNode> path2 = paths.get(1);
        for (int i = path1.size() - 1; i >= 0; i--) {
            if (path2.contains(path1.get(i))) {
                return path1.get(i);
            }
        }
        return null;
    }

    public void dfs(TreeNode root, TreeNode target) {
        if (root == target) {
            tmpPath.add(root);
            paths.add(new ArrayList<>(tmpPath));
            return;
        }
        tmpPath.add(root);
        if (root.left != null) dfs(root.left, target);
        if (root.right != null) dfs(root.right, target);
        tmpPath.remove(tmpPath.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3, new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))), new TreeNode(1, new TreeNode(0), new TreeNode(8)));
        System.out.println(new Leetcode_236().lowestCommonAncestor(root, root.left, root.left.right.right).val);
    }

}